package leetcode_zh

import (
	"math"
	"math/rand"
	"strconv"
	"time"
)

/**
 * @Description: 29. 两数相除 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/29 18:29
 **/
func divide(dividend int, divisor int) int {
	if divisor == 1 && dividend == -2147483648 {
		return -2147483648
	}
	var positive = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)
	if dividend < 0 {
		dividend = -dividend
	}
	if divisor < 0 {
		divisor = -divisor
	}
	if dividend == 0 || divisor > dividend {
		return 0
	}
	if dividend < 0 {
		dividend = -dividend
	}
	if divisor < 0 {
		divisor = -divisor
	}
	var res = 1
	var plus = divisor
	for dividend > divisor {
		divisor += divisor
		res <<= 1
		if res >= math.MaxInt32 {
			res = math.MaxInt32
			divisor = -1
			break
		}
	}

	for divisor > dividend {
		divisor -= plus
		res--
	}

	if positive {
		return res
	}
	return -res

}

/**
 * @Description: 36. 有效的数独
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/29 19:12
 **/
func isValidSudoku(board [][]byte) bool {
	var rowMap = make([]map[byte]bool, 9)
	var cloMap = make([]map[byte]bool, 9)
	var cubeMap = make([]map[byte]bool, 9)

	for i := 0; i < 9; i++ {
		rowMap[i] = make(map[byte]bool)
		cloMap[i] = make(map[byte]bool)
		cubeMap[i] = make(map[byte]bool)
	}
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			var cubePosI = getIdx(i, j)
			if rowMap[i][board[i][j]] || cloMap[j][board[i][j]] || cubeMap[cubePosI][board[i][j]] {
				return false
			}
			if board[i][j] == '.' {
				continue
			}
			rowMap[i][board[i][j]] = true
			cloMap[j][board[i][j]] = true
			cubeMap[cubePosI][board[i][j]] = true
		}
	}
	return true
}

func getIdx(i, j int) int {
	switch {
	case i/3 == 0 && j/3 == 0:
		return 0
	case i/3 == 0 && j/3 == 1:
		return 1
	case i/3 == 0 && j/3 == 2:
		return 2
	case i/3 == 1 && j/3 == 0:
		return 3
	case i/3 == 1 && j/3 == 1:
		return 4
	case i/3 == 1 && j/3 == 2:
		return 5
	case i/3 == 2 && j/3 == 0:
		return 6
	case i/3 == 2 && j/3 == 1:
		return 7
	case i/3 == 2 && j/3 == 2:
		return 8
	}
	return 0
}

/**
 * @Description: 38. 外观数列 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/1 8:39
 **/
func countAndSay(n int) string {
	if n == 1 {
		return "1"
	}
	if n == 2 {
		return "11"
	}
	var preStr = "11"
	for i := 3; i <= n; i++ {
		var curStr string
		size := len(preStr)
		var curCnt = 1
		for j := 1; j < size; j++ {
			if j == size-1 {
				if preStr[j] != preStr[j-1] {
					curStr += (strconv.Itoa(curCnt)) + string(preStr[j-1]) + "1" + string(preStr[j])
					break
				} else {
					curStr += (strconv.Itoa(curCnt + 1)) + string(preStr[j-1])
					break
				}
			}
			if preStr[j] != preStr[j-1] {
				curStr += (strconv.Itoa(curCnt)) + string(preStr[j-1])
				curCnt = 1
			} else {
				curCnt++
			}
		}
		preStr = curStr
	}
	return preStr
}

/**
 * @Description: 215. 数组中的第K个最大元素 中等
 * @Keyword: 2种方法，1最小堆法 2基于快速排序的选择法
 * @Author: kami
 * @Date: 2022/6/1 10:59
 **/
func findKthLargestQuickSelect(nums []int, k int) int {
	// 设置随机种子
	rand.Seed(time.Now().UnixNano())
	return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}

func quickSelect(a []int, l, r, index int) int {
	// 随机在 a-l之间选取一个数字作为下标
	q := randomPartition(a, l, r)
	if q == index {
		return a[q]
	} else if q < index {
		return quickSelect(a, q+1, r, index)
	}
	return quickSelect(a, l, q-1, index)
}

func randomPartition(a []int, l, r int) int {
	// 随机选下标
	i := rand.Int()%(r-l+1) + l
	// 交换随机下标值与右侧值
	a[i], a[r] = a[r], a[i]
	// 分区
	return partition(a, l, r)
}

func partition(a []int, l, r int) int {
	// 选取右值作为锚点值
	x := a[r]
	i := l - 1
	// 左小右大
	for j := l; j < r; j++ {
		// 比锚点值小的放左边，依次排列
		if a[j] <= x {
			i++
			a[i], a[j] = a[j], a[i]
		}
	}
	//将锚点值放中间
	a[i+1], a[r] = a[r], a[i+1]
	// 返回中间坐标
	return i + 1
}

/**
 * @Description: 215. 数组中的第K个最大元素 中等
 * @Keyword: 2种方法，1最小堆法 2基于快速排序的选择法
 * @Author: kami
 * @Date: 2022/6/1 10:59
 **/
func findKthLargest215(nums []int, k int) int {
	heapSize := len(nums)
	buildMaxHeap(nums, heapSize)
	for i := len(nums) - 1; i >= len(nums)-k+1; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		heapSize--
		maxHeapify(nums, 0, heapSize)
	}
	return nums[0]
}

func buildMaxHeap(a []int, heapSize int) {
	for i := heapSize / 2; i >= 0; i-- {
		maxHeapify(a, i, heapSize)
	}
}

func maxHeapify(a []int, i, heapSize int) {
	l, r, largest := i*2+1, i*2+2, i
	if l < heapSize && a[l] > a[largest] {
		largest = l
	}
	if r < heapSize && a[r] > a[largest] {
		largest = r
	}
	if largest != i {
		a[i], a[largest] = a[largest], a[i]
		maxHeapify(a, largest, heapSize)
	}
}

/**
 * @Description: 338. 比特位计数 简单
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/6/12 12:44
 **/
func countBits(n int) []int {
	var dp = make([]int, n+1)
	for i := 0; i <= n; i++ {
		if i%2 == 0 {
			dp[i] = dp[i/2]
		} else {
			dp[i] = dp[i/2] + 1
		}
	}
	return dp
}

/**
 * @Description: 448. 找到所有数组中消失的数字 简单
 * @Keyword: 利用下标与数值的映射
 * @Author: kami
 * @Date: 2022/6/12 12:54
 **/
func findDisappearedNumbers(nums []int) []int {
	var seen = make([]int, len(nums)+1)
	for i := 0; i < len(nums); i++ {
		if seen[nums[i]] == 0 {
			seen[nums[i]] = 1
		}
	}
	var res []int
	var seenLen = len(nums) + 1
	for i := 1; i < seenLen; i++ {
		if seen[i] == 0 {
			res = append(res, i)
		}
	}
	return res
}

/**
 * @Description: 279. 完全平方数 中等 https://leetcode.cn/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode-solut-t99c/
 * @Keyword: 任何正整数都可以拆分成不超过4个数的平方和 ---> 答案只可能是1,2,3,4
			 如果一个数最少可以拆成4个数的平方和，则这个数还满足 n = (4^a)*(8b+7) ---> 因此可以先看这个数是否满足上述公式，如果不满足，答案就是1,2,3了
			 如果这个数本来就是某个数的平方，那么答案就是1，否则答案就只剩2,3了
			 如果答案是2，即n=a^2+b^2，那么我们可以枚举a，来验证，如果验证通过则答案是2
			 只能是3
 * @Author: kami
 * @Date: 2022/6/26 10:05
 **/
func numSquares(n int) int {
	if isPerfectSquare(n) {
		return 1
	}
	if checkAnswer4(n) {
		return 4
	}
	for i := 1; i*i <= n; i++ {
		j := n - i*i
		if isPerfectSquare(j) {
			return 2
		}
	}
	return 3
}

// 判断是否为完全平方数
func isPerfectSquare(x int) bool {
	y := int(math.Sqrt(float64(x)))
	return y*y == x
}

// 判断是否能表示为 4^k*(8m+7)
func checkAnswer4(x int) bool {
	for x%4 == 0 {
		x /= 4
	}
	return x%8 == 7
}
